package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC1139 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目参考了别人代码
     * 这是因为问题情况较为复杂,自己写又嫌麻烦，就抄了答案
     * 未来需要再次复习此道题目
     * @return:
     */
    class Solution {
        public int largest1BorderedSquare(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            //dp[i][j][0]: i,j左边连续的1的个数
            //dp[i][j][1]: i,j上边连续的1的个数
            int[][][] dp = new int[m + 1][n + 1][2];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (grid[i - 1][j - 1] == 1) {
                        dp[i][j][0] = 1 + dp[i][j - 1][0];
                        dp[i][j][1] = 1 + dp[i - 1][j][1];
                    }
                }
            }
            int res = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    //最短的那条边不一定是合法的边长，如果该边长不合法就需要缩减边长，直到找到合法的
                    for (int side = Math.min(dp[i][j][0], dp[i][j][1]); side >= 1; side--) {
                        if (dp[i][j - side + 1][1] >= side && dp[i - side + 1][j][0] >= side) {
                            res = Math.max(res, side);
                            break; //更短的就没必要考虑了
                        }
                    }
                }
            }
            return res * res;
        }
    }

    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1139 an = new LC1139();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
